<?php

/**
  * AVL-tree implementation (in C++) taken from:
  * http://en.wikibooks.org/wiki/Algorithm_Implementation/Trees/AVL_tree
  * and modified/converted into PHP
  */
class AvlTree {
	private $root;

	public function __construct(Node $root = null) {
		$this->setRoot($root);
	}

	public function getRoot() {
		return $this->root;
	}

	public function setRoot(Node $root = null) {
		$this->root = $root;
		if ($root != null) {
			$root->setParent(null);
		}
	}

	public function search($value) {
		$temp = $this->root;
		while ($temp != null) {
			if ($value == $temp->getValue()) {

				return $temp;
			} else 	if ($value < $temp->getValue()) {
				$temp = $temp->getLeftChild();
			} else {
				$temp = $temp->getRightChild();
			}
		}

		return null;
	}

	public function insert($value) {
		$node = new Node($value);

		if ($this->root == null) {
			$this->root = $node;

			return true;
		}

		$temp = $this->root;

		while (true) {
			if ($temp->getValue() > $value) {
				if ($temp->getLeftChild() != null) {
					$temp = $temp->getLeftChild();
				} else {
					$temp->setLeftChild($node);
					break;
				}
			} else if ($temp->getValue() < $value) {
				if ($temp->getRightChild() != null) {
					$temp = $temp->getRightChild();
				} else {
					$temp->setRightChild($node);
					break;
				}
			} else {
				/* The node with the $value already exists */
				return false;
			}
		}

		$temp = $node;

		/* Re-balance the tree */
		while ($temp != null) {
			$temp->updateHeight();
			$this->balanceSubtree($temp);
			$temp = $temp->getParent();
		}

		return true;
	}

	public function balanceSubtree(Node $node) {
		$balance = $node->getBalance();
		//ho $node->getValue() . ' and balance ' . $balance . '<br>';		
		if ($balance < -1) {
			$leftLeftChild = $node->getLeftChild()->getLeftChild();
			$leftRightChild = $node->getLeftChild()->getRightChild();
			/* LEFT LEFT CASE */
			if (
				$leftLeftChild != null && $leftRightChild != null &&
				$leftLeftChild->getHeight() >= $$leftRightChild->getHeight()
			) {
				$this->rotateLeft($node->getLeftChild());
			}
			$this->rotateRight($node);
		} else if ($balance > 1) {
			$rightLeftChild = $node->getRightChild()->getLeftChild();
			$rightRightChild = $node->getRightChild()->getRightChild();

			if (
				$rightLeftChild != null && $rightRightChild != null &&
				$rightRightChild->getHeight() < $rightLeftChild->getHeight()
			) {
				$this->rotateRight($node->getRightChild());
			}
			$this->rotateLeft($node);
		}
	}

	public function rotateLeft(Node $node) {
		$parent = $node->getParent();
		$left = true;
		if ($parent != null && $parent->getRightChild() == $node) {
			$left = false;
		}

		$temp = $node->getRightChild();
		$node->setRightChild($temp->getLeftChild());
		$temp->setLeftChild($node);

		if ($parent != null) {
			if ($left) {
				$parent->setLeftChild($temp);
			} else {
				$parent->setRightChild($temp);
			}

		} else {
			$this->setRoot($temp);
		}
	}

	public function rotateRight(Node $node) {
		$parent = $node->getParent();
		$temp = $node->getLeftChild();
		$node->setRightChild($temp->getRightChild());
		$temp->setRightChild($node);


		$left = true;
		if ($parent != null && $parent->getRightChild() == $node) {
			$right = true;
		}

		if ($parent != null) {
			if ($left) {
				$parent->setLeftChild($temp);
			} else {
				$parent->setRightChild($temp);
			}
		} else {
			$this->setRoot($temp);
		}

	}

	public function leftRightRotate(Node $node) {
		$this->rotateLeft($node->getLeftChild());
		$this->rotateRight($node);
	}

	public function rightLeftRotate(Node $node) {
		$this->rotateRight($node->getRightChild());
		$this->rotateLeft($node);
	}

	public function deleteNode(Node $node) {
		$node->__destruct();
		unset($node);
	}

	public function delete($value) {
		if ($this->root == null) {

			return false;
		}

		$deletableNode = $this->search($value);
		if ($deletableNode == null) {
			return false;
		}

		$parent == $deletableNode->getParent();
		$left = true;
		if ($parent != null && $parent->getRightChild() == $deletableNode) {
			$left = false;
		}

		if ($deletableNode->getLeftChild() == null && $deletableNode->getRightChild() == null) {

			if ($parent != null) {
				if ($left) {
					$parent->setLeftChild(null);
				} else {
					$parent->setRightChild(null);
				}

				$this->deleteNode($deletableNode);

				$parent->updateHeight();
				$this->balanceSubtree($parent);
			} else {
				$this->setRoot(null);
				/* @FIXME: don't know if this works */
				$this->deleteNode($deletableNode);
			}

		} else if ($deletableNode->getRightChild() == null) {

			if ($parent != null) {
				if ($left) {
					$parent->setLeftChild($deletableNode->getLeftChild());
				} else {
					$parent->setRightChild($deletableNode->getLeftChild());
				}

				$this->deleteNode($deletableNode);
				$parent->updateHeight();
				$this->balanceSubtree($parent);
			} else {
				$this->setRoot($deletableNode->getLeftChild());
				$this->deleteNode($deleteNode);
			}
		} else if ($deletableNode->getLeftChild() == null) {

			if ($parent != null) {
				if ($left) {
					$parent->setLeftChild($deletableNode->getRightChild());
				} else {
					$parent->setRightChild($deletableNode->getRightChild());
				}

				$this->deleteNode($deletableNode);
				$parent->updateHeight();
				$this->balanceSubtree($parent);
			} else {
				$this->setRoot($deletableNode->getRightChild());
				$this->deleteNode($deletableNode);
			}
		} else {

			$balance = $deletableNode->getBalance();
			if ($balance > 0) {
				if ($deletableNode->getLeftChild()->getRightChild() == null) {
					$replacement = $deletableNode->getLeftChild();
					$replacement->setRightChild($deletableNode->getRightChild());

					$temp = $replacement;
				} else {
					$replacement = $deletableNode->getLeftChild()->getRightChild();
					while ($replacement->getRightChild() != null) {
						$replacement = $replacement->getRightChild();
					}
					$replacementParent = $replacement->getParent();
					$replacementParent->setRightChild($replacement->getLeftChild());

					$temp = $replacementParent;

					$replacement->setLeftChild($deletableNode->getLeftChild());
					$replacement->setRightChild($deletableNode->getRightChild());
				}
			} else {
				if ($deletableNode->getRightChild()->getLeftChild() == null) {
					$replacement = $deletableNode->getRightChild();
					$replacement->setRightChild($deletableNode->getLeftChild());

					$temp = $replacement;
				} else {
					$replacement = $deletableNode->getRightChild()->getLeftChild();
					while ($replacement->getLeftChild() != null) {
						$replacement = $replacement->getLeftChild();
					}
					$replacementParent = $replacement->getParent();
					$replacementParent->setLeftChild($replacement->getRightChild());

					$temp = $replacementParent;

					$replacement->setLeftChild($deletableNode->getLeftChild());
					$replacement->setRightChild($deletableNode->getRightChild());
				}
			}

			if ($parent != null) {
				if ($left) {
					$parent->setLeftChild($replacement);
				} else {
					$parent->setRightChild($replacement);
				}
				$this->deleteNode($deletableNode);
			} else {
				$this->setRoot($replacement);
				$this->deleteNode($deletableNode);
			}

			$this->balanceSubtree($temp);
		}


	}
}